package com.yiwenup.leetcode.offer;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.Set;

/**
 * https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
 **/
public class No038 {

    /**
     * 执行用时：7 ms, 在所有 Java 提交中击败了90.12%的用户
     * 内存消耗：46.5 MB, 在所有 Java 提交中击败了5.85%的用户
     */
    public String[] permutation(String s) {
        List<String> res = new LinkedList<>();
        // 深度优先
        dfs(0, s.toCharArray(), res);
        return res.toArray(new String[0]);
    }

    private void dfs(int idx, char[] arr, List<String> res) {
        if (idx == arr.length - 1) {
            // 每遍历到结尾为一组排列方式
            res.add(String.valueOf(arr));
            return;
        }

        Set<Character> visited = new HashSet<>();
        for (int i = idx; i < arr.length; i++) {
            if (visited.contains(arr[i])) continue;
            visited.add(arr[i]);

            swap(i, idx, arr);
            dfs(idx + 1, arr, res);
            swap(idx, i, arr);
        }
    }

    private void swap(int idx1, int idx2, char[] arr) {
        char tmp = arr[idx1];
        arr[idx1] = arr[idx2];
        arr[idx2] = tmp;
    }
}
